//括号匹配问题，可以引入unorder_map匹配

#include <iostream>
#include <stack>
#include <unordered_map>
#include <string>

bool isValid(std::string s)
{
    int n = s.size();
    // 不是双数的话
    if (n % 2 != 0)
        return false;

    std::unordered_map<char, char> map = {
        {')', '('},
        {']', '['},
        {'}', '{'}};

    std::stack<int> st;
    for (int i = 0; i < n; i++)
    {
        // 如果是右括号
        if (map.count(s[i]))
        {
            // 栈为空，不匹配，
            if (st.empty() || st.top() != map[s[i]])
                return false;
            // 匹配
            else
                st.pop();
        }
        // 左括号
        else
        {
            st.push(s[i]);
        }
    }
    return st.empty();
}